package com.ruoyi.util;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

import cn.hutool.core.collection.ListUtil;

/**
 * @Description: 一些常用的排序
 * @ClassName: Shortnumber
 * @author syc
 * @date: 2022年6月3日 上午10:20:46
 */
public class Shortnumber {

    /**
     * @Description:冒泡排序 
     * @author syc
     * @date: 2022年7月21日 下午2:44:51
     */
    public static void mppx(int[] arr) {
    	int[] a =  Arrays.copyOf(arr, arr.length);
    	int len = a.length;
        int zj;
        boolean bol;
        // 注意第一个循环的 i =1, 而不是0;
    	for (int i = 1; i < len; i++) {
    		bol = true;
			for (int j = 0; j < (len - i); j++) {
				if (a[j] > a[j + 1]) {
					zj = a[j];
					a[j] = a[j + 1];
					a[j + 1] = zj;
					if (bol) {
						bol = false;
					}
				}
			}
    		if (bol) {
    			break;
    		}
    	}
    	for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + ",");
		}
    }
	
    /**
     * @Description: 选择排序
     * @author syc
     * @date: 2022年7月21日 下午2:45:48
     */
    public static int[] xzpx(int[] arr) {
    	int[] a = Arrays.copyOf(arr, arr.length);
    	int len = arr.length;
    	for (int i = 0; i < len; i++) {
    		int min = i;
			for (int j = i + 1; j < len; j++) {
				if (a[j] < a[min])  {
				    min = j;	
				}
			}
			if (i != min) {
				int tep = a[i];
				a[i] = a[min];
				a[min] = tep;
			}	
		}
    	return a;
    }
    
	
	
    // 插入排序1 (这种写法没有错但是,阅读起来比较费劲)
    public static int[] crpx(int[] arr) {
    	int[] a = Arrays.copyOf(arr, arr.length);
    	int len = arr.length;
    	int s = 0;
    	for (int i = 1; i < len ; i++) {
    		s = a[i];
    		for (int j = i-1; j > -1; j--) {
				if (a[j] < s) {
					a[j + 1] = s;
					break;
				}
				a[j + 1] = a[j];
				if(j == 0) {
					a[j] = s;
				}
			}	
		}
    	return a;
    }
    
    // 插入排序2 
    
    public static int[] crpx2(int[] arr) {
    	int[] a = Arrays.copyOf(arr, arr.length);
    	int len = a.length;
//    	int s;
//    	int j;
    	for (int i = 1; i < len ; i++) {
    		int s = a[i];
    		int j = i;
    		while (j > 0 && a[j-1] > s) {
				a[j] = a[j-1];
    			j--;
			}
    		if (j < i) {
    			a[j] = s;
    		}
    	}
    	return a;
    }
    
    /**
     * @Description: 希尔排序
     * @author syc
     * @date: 2022年7月25日 下午5:06:04
     * 	希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，
     *	待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。
     */
    public static int[] shellSort(int[] a) {
    	int[] arr = Arrays.copyOf(a, a.length);
        int length = arr.length;
        int temp;
        // {6,5,4,3,2,1};
        for (int step = length / 2; step >= 1; step /= 2) {
        	System.out.println(step + "....111111");
            for (int i = step; i < length; i++) {
                temp = arr[i];
                int j = i - step;
                while (j >= 0 && arr[j] > temp) {
                    arr[j + step] = arr[j];
                    j -= step;
                }
                arr[j + step] = temp;
            }
        }
        return arr;
    }
    
  public static List<Integer> shellSort( List<Integer> list) {
      int length = list.size();
      int temp;
      // {6,5,4,3,2,1};
      for (int step = length / 2; step >= 1; step /= 2) {
      	System.out.println(step + "....111111");
          for (int i = step; i < length; i++) {
              temp = list.get(i);
              int j = i - step;
              while (j >= 0 && list.get(j) > temp) {
            	  list.set((j + step), list.get(j));
                  j -= step;
              }
              list.set((j + step), temp);
              System.out.println("内层..." + list.toString());    
          }
          System.out.println("外层..." + list.toString());      
      }
      return list;
  }  

  
//	public static void main(String[] args) {
//		List<Integer> list = new ArrayList<Integer>(); 
//		list.add(9);
//		list.add(8);
//		list.add(7);
//		list.add(6);
//		list.add(5);
//		list.add(4);
//		list.add(3);
//		
//		
//		list = shellSort(list);
//		
//		
//		System.out.println(list.toString());
//		
////		int[] a = {6,5,4,3,2,1};
////		int[] b = shellSort(a);
////		for (int i : b) {
////			System.out.print(i + ",");
////		}
//	}

	
	
	
	
	
	
	
	
	
}
